# -*- coding:utf-8 -*-
'''
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路：首先递归先序遍历找到开始的根节点，然后再次开始判断左右子树是否相同
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        flag = False
        if not pRoot2 or not pRoot1: return False
        if pRoot2.val == pRoot1.val:
            flag = self.isEqual(pRoot1, pRoot2)
        if flag is False:
            flag = self.HasSubtree(pRoot1.left, pRoot2)
        if flag is False:
            flag = self.HasSubtree(pRoot1.right, pRoot2)
        return flag

    def isEqual(self, r1, r2):
        if not r2: return True
        if not r1: return False
        if r1.val != r2.val:
            return False
        else:
            return self.isEqual(r1.left, r2.left) and self.isEqual(r1.right, r2.right)

    # 先序遍历比较法
    def HasSubtree_1(self, pRoot1, pRoot2):
        # write code here
        self.preTree(pRoot1)
        pr1 = self.stack
        self.stack = []
        self.preTree(pRoot2)
        pr2 = self.stack
        if pr1 is None or pr2 is None:
            return False
        pr1 = map(str, pr1)
        pr2 = map(str, pr2)
        pr1 = ''.join(pr1)
        pr2 = ''.join(pr2)
        if pr1.find(pr2):
            return True
        else:
            return False

    def preTree(self, pRoot):
        if pRoot:
            self.stack.append(pRoot.val)
        if pRoot.left is None and pRoot.right is None:
            return pRoot
        if pRoot.left:
            self.preTree(pRoot.left)
        if pRoot.right:
            self.preTree(pRoot.right)

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)

a.left = b
a.right = c

s = Solution()
if s.HasSubtree(a, c):
    print(11111)

